package com.zql.LeetCode;

/**
 * Created By ShuHua on 2021/9/29.
 */
public class ShipWithinDays_1011 {
    //left和right的取值范围
    //left:由题意知每一个包裹不可分割，因此船的最小载重量是包裹的最大重量，每次至少装一个包裹
    //right:假设船需要在一天之内运完所有包裹那么船的载重量至少是所有包裹的总和，因此right取所有包裹的总和即可，一次吧所有货物装走
    public static int shipWithinDays(int[] weights, int days){
        int[] maxAndTotal = getMAxAndTotla(weights);
        int left = maxAndTotal[0];
        int right = maxAndTotal[1];
        while (left<=right){//left=right+1
            int mid = left+(right-left)/2;
            int result = days(weights,mid);
            if(result==days){
                right=mid-1;
            }else if(result>days){
                left = mid+1;
            }else if(result<days){
                right = mid-1;
            }
        }
        return left;
    }

    /**
     * 根据运载能力求运完所有包裹的时间
     * 运载量越大，装完货所需的时间越小。单调递减函数
     * @param weights
     * @param capability
     * @return
     */
    public static int days(int[] weights, int capability){
        int sum =0;
        int days= 0;
        for(int i=0;i<weights.length;i++){
            sum+=weights[i];
            if(i==weights.length-1&&sum<capability){
                days++;
            }
            if(sum>capability){
                sum=0;
                days++;
                i--;
            }else if(sum==capability){
                days++;
                sum=0;
            }

        }
        return days;
    }
    public static int[] getMAxAndTotla(int[] weights){
        int max =weights[0];
        int sum =weights[0];
        for(int i=1;i<weights.length;i++){
            sum+=weights[i];
            if(weights[i]>max)max=weights[i];
        }
        return new int[]{max,sum};
    }

    public static void main(String[] args) {
        int[] weights ={1,2,3,4,5,6,7,8,9,10};
        int day = days(weights,55);
        System.out.println(day);
//        int result = shipWithinDays(weights,1);
//        System.out.println(result);

    }
}
